package Practice;

import java.util.*;

/**
 * Description:
 * Date: 2025-11-10
 * Time: 15:12
 */
public class Practice {

    //有效的括号  https://leetcode.cn/problems/valid-parentheses/
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            }
            if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.empty()) {
                    return false;
                }
                char s1 = stack.peek();
                if ((s1 == '(' && ch == ')') || (s1 == '{' && ch == '}') || (s1 == '[' && ch == ']')) {
                    stack.pop();
                }else {
                    return false;
                }
            }

        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }

    //逆波兰求值  https://leetcode.cn/problems/evaluate-reverse-polish-notation/
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
                Integer val1 = stack.pop();
                Integer val2 = stack.pop();
                Integer sum = 0;
                switch (str) {
                    case "+":
                        sum = val1 + val2;
                        break;
                    case "-":
                        sum = val2 - val1;
                        break;
                    case "*":
                        sum = val1 * val2;
                        break;
                    case "/":
                        sum = val2 / val1;
                }
                stack.push(sum);
            }else {
                int a = Integer.parseInt(str);
                stack.push(a);
            }
        }
        return stack.pop();
    }

    // 栈的压入、弹出序列  https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            //这里用上循环是必要的，为了配合for循环的循环条件
            while (!stack.isEmpty() && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }




    public static void main(String[] args) {

    }
}
